Dynamic Segment Tree
Operations
モノイド$ Mの列$ (a_1, a_2, \dots, a_n)を扱う.
追加した要素の数を$ m とすると空間計算量$ \Theta(m (\log n - \log m + 1))
$ \mathtt{new}()
列の項がすべて$ Mの単位元であるSegment Treeを作成する.
時間計算量$ \Theta(1)
$ \mathtt{set}(i, x)
$ a_iに$ xを代入する.
時間計算量$ \Omicron(\log n)
空間計算量$ \Omicron(\log n)
$ \mathtt{fold}(l, r)
$ a_l \cdot a_{l+1} \cdot \dots \cdot a_rを計算する.
時間計算量$ \Omicron(\log n)
Summary
単位元ではない要素の部分だけ作る Segment Tree
References
Notes
$ \mathtt{set}(i, x)のノードの作成時に,$ i = l = r - 1が成り立つまでノードを作成し続けるのではなく,子が一つだけが葉まで続く部分は省略してノードの作成数を抑えることができる.
$ i = l = r - 1まで続ける実装: 240ms #361780 Patricia Treeを使うと空間計算量が$ \Theta(m (\log n - \log m + 1))から$ \Theta(m)に落ちる. Implementations
Problems
クエリ先読み+座圧をサボることができる
imos法